In the conventional Von Neumann computer architecture, memory is structured as a linear array of fixed-size cells, indexed by sequential addresses. FIG. 1 shows an example of this conventional architecture. Execution of instructions 102 results in contents of memory 104 being as shown. Although this approach is simple to implement, and is relatively easy to use for fixed-sized application data units, software structures and techniques are required to handle variable-sized and structured data.
With variable-sized data, software typically implements a dynamic memory allocator that locates a contiguous region of the memory that is at least as large as that requested. However, over the course of extended execution, the memory space can become fragmented into smaller regions so that a memory allocation request fails even though the total amount of memory available is ample. Mechanisms such as generational garbage collectors can re-compact memory periodically by copying regions to make them contiguous but such garbage collection can interfere with the on-going execution of the application when invoked, an aspect not acceptable in real-time systems in particular or ones requiring predictable response in general. Moreover, if a variable-size data item grows in length, software must allocate a new contiguous region of the required size and copy the data to the new location and change all references pointing to the old location to now point to the new location. To facilitate this latter action, some software introduces an extra level of indirection through a fixed size location that provides the actual pointer to the variable-sized data, so there is a single location to update, but at the cost of an extra indirection on each access.
An alternative approach to variable-sized data is to construct the variable-sized data types from non-contiguous memory units using pointers (i.e., use structured data). Structured data is challenging to handle because it is difficult to determine when a memory region can be freed in the presence of the complicated pointer references characteristic of structured data. Access to data in a structured data representation also incurs the overhead of indirecting through pointers to fix the next entry in a variable-size data item.
For applications running in multiple separate processes, structured data introduces further overhead because it is generally necessary to serialize structured data and copy the result to a separate address space and then de-serialize it in order to share the structured data. This arises because the addresses used to structure the data are unique to each address space as a result of the virtual address translation used to provide isolation between processes. Sharing is further impeded by the large granularity of memory pages (e.g., 8 kilobyte or larger) used for address translation in comparison to typical application data units (e.g. 32-128 bytes). As a consequence, applications are either organized as multiple threads within one process, forgoing the protection of separate addresses or else pay a significant penalty in serializing, copying and de-serializing structured data between address spaces.
Recent and anticipated technology developments make the disadvantages of this standard Von Neumann model much more problematic. First of all, memory system performance has not kept pace with increased processor performance, making memory performance an increasingly limiting factor for computer performance. Thus, memory-intensive operations such as copying and garbage collection are becoming proportionally more expensive. Caching has been the primary means to deal with the processor/memory speed mismatch. However, with increasing sizes of memory, larger and more complex application objects and more data-intensive applications, caches are becoming significantly less effective using this conventional memory model.
As a second direction, computer hardware is increasingly relying on parallel execution to achieve performance benefits. In particular, it is feasible to implement multiple “cores” on a single microchip, improving cost-efficiency while allowing sharing of memory controller and cache. However, the extra copying induced by structured data leads to inefficient use of caches because of duplicated data. Moreover, extraneous updates such as reference count updates and false sharing in cache lines with updates leads to further memory and cache inefficiencies.
As a final trend, applications are becoming larger and more complex, enabled by increased memory sizes and processor performance, but increasing the difficulty of maintaining software correctness, especially with demands for on-going improvements and features. At the same time, applications are taking on increasingly time-, mission- and even life-critical functions, making their reliability that much more important.
For these and other reasons, alternative memory architectures have been considered. For example, in U.S. Pat. No. 4,989,137, a user processor accesses memory exclusively by way of a binding register unit which is part of a memory management system. In this manner, the memory management system can hide low level details of physical memory organization from the user processor, and instead presents a logical memory abstraction to the user processor. In U.S. Pat. No. 4,695,949, a block oriented memory is described, where a reference count is maintained for each block, thereby alleviating the need for frequent garbage collection.
In U.S. Pat. No. 5,784,699, a block-oriented memory system having several standard block sizes is considered. Memory allocation requests are rounded up to the nearest standard block size. In U.S. Pat. No. 5,950,231, a block-oriented memory management system controlled with a stack of pointers is considered. In U.S. Pat. No. 5,247,634 and U.S. Pat. No. 5,864,867, memory management based on the use of trees is considered.
However, these preceding approaches, and the standard Von Neumann cache approach, both tend to have difficulties, particularly for structured data. Accordingly, it would be an advance in the art to provide improved memory management, especially for variable-sized and structured data.